package huawei;
/*
* @Author: wanghongfucoder
* @Date:   2017-06-27 11:13:52
* @Last Modified by:   wanghongfucoder
* @Last Modified time: 2017-06-27 13:26:33
*/

public class ShortPath {
	public static void main(String[] args) {
		//矩阵路径图
		int[][] arr={{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};
		 int result=shortpath(arr);
        System.out.println(result);
	}

	public static  int  shortpath(int[][] arr) {
		int[][] result=new int [arr.length][arr.length];
		for (int i=0;i<arr.length ;i++ ) {
			if (i==0) {
				result[0][0]=arr[0][0];
			}else{
				result[0][i]=result[0][i-1]+arr[0][i];
				result[i][0]=result[i-1][0]+arr[i][0];
			}
		}
		for (int i=1; i<arr.length;i++) {
			for (int j=1; j<arr.length; j++) {
				result[i][j]=Math.min(result[i-1][j],result[i][j-1])+arr[i][j];
			}
		}
		return result[arr.length-1][arr.length-1];
	}
}